#include<iostream>
#include<string>
#include<bitset>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int f1[N], f2[N];
string s;
int n;
int main()
{
	int t;
	cin >> t;
	while (t--) {
		cin >> n;
		int cnt = 0;
		int ans = 0;
		bool flag = 0;
		for (int i = 0; i <= 31; i++) {
			ans += (int)pow(2, i);
			if (ans > n)break;
			if (ans == n) {
				flag = 1;
				break;
			}
		}
		if (flag)cout << 1 << endl;
		else cout << 0 << endl;
		//cout << cnt - 1 << endl;
		/*for (int i = 31; i >= 0; i--) {
			if ((n >> i) & 1) {
				cnt = i;
				break;
			}
		}
		cout << cnt - 1 << endl;*/
	}
	return 0;
}